0318. 最大单词长度乘积【中等】
1. 📝 题目描述
给你一个字符串数组 words，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0。
示例 1：
txt
输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16
解释：这两个单词为 "abcw", "xtfn"。1
2
3
2
3
示例 2：
txt
输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4
解释：这两个单词为 "ab", "cd"。1
2
3
2
3
示例 3：
txt
输入：words = ["a","aa","aaa","aaaa"]
输出：0
解释：不存在这样的两个单词。1
2
3
2
3
提示：
2 <= words.length <= 10001 <= words[i].length <= 1000words[i]仅包含小写字母
2. 🎯 s.1 - 位运算
c
int maxProduct(char** words, int wordsSize) {
int* masks = (int*)calloc(wordsSize, sizeof(int));
for (int i = 0; i < wordsSize; i++) {
for (int j = 0; words[i][j]; j++)
masks[i] |= 1 << (words[i][j] - 'a');
}
int res = 0;
for (int i = 0; i < wordsSize; i++) {
int li = strlen(words[i]);
for (int j = i + 1; j < wordsSize; j++) {
if ((masks[i] & masks[j]) == 0) {
int val = li * (int)strlen(words[j]);
if (val > res) res = val;
}
}
}
free(masks);
return res;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
js
/**
* @param {string[]} words
* @return {number}
*/
var maxProduct = function (words) {
const n = words.length
const masks = new Array(n)
for (let i = 0; i < n; i++) {
masks[i] = 0
for (const ch of words[i]) masks[i] |= 1 << (ch.charCodeAt(0) - 97)
}
let res = 0
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if ((masks[i] & masks[j]) === 0) {
res = Math.max(res, words[i].length * words[j].length)
}
}
}
return res
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
py
class Solution:
def maxProduct(self, words: List[str]) -> int:
masks = [0] * len(words)
for i, w in enumerate(words):
for ch in w:
masks[i] |= 1 << (ord(ch) - 97)
res = 0
for i in range(len(words)):
for j in range(i + 1, len(words)):
if masks[i] & masks[j] == 0:
res = max(res, len(words[i]) * len(words[j]))
return res1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
- 时间复杂度：
- 空间复杂度：
算法思路：
- 每个单词用 26 位的位掩码表示其包含的字母
- 两两比较，若掩码按位与为 0 则无公共字母，更新最大乘积